#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;

// 71.80 %
class Solution1
{
  public:
	vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
	{
		vector<int> myVec1;
		for (int i = 0; i < nums1.size(); i++)
		{
			for (int j = 0; j < nums2.size(); j++)
			{
				if (nums1[i] == nums2[j])
				{
					myVec1.push_back(nums1[i]);
					nums2.erase(nums2.begin() + j);
					break;
				}
			}
		}
		return myVec1;
	}
};

// 100.00 %
class Solution2
{
  public:
	vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
	{
		map<int, int> record;
		for (int i = 0; i < nums1.size(); i++)
			record[nums1[i]]++;
		vector<int> resultVector;
		for (int i = 0; i < nums2.size(); i++)
			if (record[nums2[i]] > 0)
			{
				resultVector.push_back(nums2[i]);
				record[nums2[i]]--;
			}
		return resultVector;
	}
};

// 71.80 %
class Solution
{
  public:
	vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
	{
		map<int, int> record;
		for (int i = 0; i < nums1.size(); i++)
			if (record.find(nums1[i]) == record.end())
				record.insert(make_pair(nums1[i], 1));
			else
				record[nums1[i]]++;
		vector<int> resultVector;
		for (int i = 0; i < nums2.size(); i++)
			if (record.find(nums2[i]) != record.end() && record[nums2[i]] > 0)
			{
				resultVector.push_back(nums2[i]);
				record[nums2[i]]--;
				if (record[nums2[i]] == 0)
					record.erase(nums2[i]);
			}
		return resultVector;
	}
};

int main()
{
	int arr1[4] = {1, 2, 2, 1};
	int arr2[2] = {2, 2};
	vector<int> myVec1(arr1, arr1 + 3);
	vector<int> myVec2(arr2, arr2 + 3);
	vector<int> re = Solution().intersect(myVec1, myVec2);
	for (int i = 0; i < re.size() - 1; i++)
	{
		cout << re[i] << " ";
	}
	cout << re[re.size() - 1] << endl;
	return 0;
}
